11401 - Triangle counting/p11401.cpp

   1 #include <iostream>
   2
   3 using namespace std;
   4
   5 unsigned long long dp[1000001];
   6
   7 inline unsigned long long cuantosNuevos(unsigned long long n){
   8   if (n == 3) return 1;
   9   if (n == 4) return 2;
  10   if (n % 2 == 0) return (n*(n-2))/4;
  11   return cuantosNuevos(n-1) + (n-1)/2;
  12 }
  13
  14 int main(){
  15   int n;
  16   dp[3] = 0;
  17   dp[4] = 1;
  18   for (int i=5; i<=1000000; ++i){
  19     dp[i] = dp[i-1] + cuantosNuevos(i-1);
  20   }
  21   while (scanf("%d", &n) == 1 && n > 2){
  22     printf("%llu\n", dp[n]);
  23   }
  24   return 0;
  25 }